package charactor

import (
	"reflect"
	"sort"
	"strings"
	"unsafe"
)

/**
最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
*/
func longestPalindrome(s string) string {
	if len(s) < 2 {
		return s
	}
	result := string(s[0])
	dp := make([][]bool, 0)
	for i := 0; i < len(s); i++ {
		tp := make([]bool, len(s))
		dp = append(dp, tp)
		dp[i][i] = true
	}
	for right := 1; right < len(s); right++ {
		for left := 0; left < right; left++ {
			rightBound := right - left + 1
			if s[right] != s[left] {
				dp[left][right] = false
			} else {
				if rightBound < 3 {
					dp[left][right] = true //只有两个字符，并且相等
				} else {
					dp[left][right] = dp[left+1][right-1]
				}
			}
			if dp[left][right] {
				//当前字串是回文串
				if len(result) < (rightBound) {
					result = s[left : right+1] //因为要取到right位 ，所以要+1
				}
			}
		}
	}
	return result
}

/**
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

*/
func convertZString(s string, numRows int) string {
	if numRows <= 1 {
		return s
	}
	curRow, scanFlag := 0, -1
	resultList := make([]strings.Builder, numRows)
	for i := 0; i < numRows; i++ {
		resultList[i] = strings.Builder{}
	}
	for _, ch := range s {
		resultList[curRow].WriteRune(ch)
		if curRow == 0 || scanFlag >= numRows {
			//重置，反向
			scanFlag *= -1
		}
		curRow += scanFlag
	}
	result := strings.Builder{}
	for _, list := range resultList {
		result.WriteString(list.String())
	}
	return result.String()
}

/**
字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。



示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

*/
func groupAnagrams(strs []string) [][]string {
	result := make(map[string][]string)
	for i := 0; i < len(strs); i++ {
		//对每一个字符串进行排序， 比如eat 排序后编程aet
		strBytes := ([]byte)(strs[i])
		sort.Slice(strBytes, func(i, j int) bool {
			if strBytes[i] < strBytes[j] {
				return true
			}
			return false
		})
		newStr := String(strBytes)
		if _, ok := result[newStr]; ok {
			result[newStr] = append(result[newStr], strs[i])
		} else {
			result[newStr] = []string{strs[i]}
		}
	}
	final := make([][]string, 0)
	for _, v := range result {
		final = append(final, v)
	}
	return final
}
func String(b []byte) (s string) {
	bytes := (*reflect.SliceHeader)(unsafe.Pointer(&b))
	pStr := (*reflect.StringHeader)(unsafe.Pointer(&s))
	pStr.Data = bytes.Data
	pStr.Len = bytes.Len
	return
}

func Slice(s string) (b []byte) {
	tmp1 := (*[2]uintptr)(unsafe.Pointer(&s))
	tmp2 := [3]uintptr{tmp1[0], tmp1[1], tmp1[1]}
	return *(*[]byte)(unsafe.Pointer(&tmp2))
}

// KMP KMP算法 实现字符串快速搜索
func KMP(haystack string, needle string) int {
	n := len(haystack)
	m := len(needle)
	if n == 0 {
		return 0
	}
	//创建next数组
	next := make([]int, m)
	for i, j := 1, 0; i < m; i++ {
		for j > 0 && needle[j] != needle[i] {
			j = next[j-1] //index=x的前缀不匹配，回退到上一个匹配的最长前缀位置
		}
		if needle[j] == needle[i] {
			j++
		}
		next[i] = j //知道字符x的最长公共前缀，回退数组next[x]=max前缀+1
	}
	//kmp查找
	for i, j := 0, 0; i < n; i++ {
		for j > 0 && haystack[i] != needle[j] {
			//匹配串回退 继续匹配
			//：：：因为时候index=j的时候好不想等，所以只能从j-1中找最长前缀进行匹配
			j = next[j-1]
		}
		if haystack[i] == needle[j] {
			//主串与字串 字符匹配，继续 向下比较
			j++
		}
		if m == j {
			//匹配完成，主串存在 sub=needle 的字串,返回匹配位置
			return i - m + 1
		}
	}
	return -1
}
